package Simple3;

import java.util.ArrayDeque;
import java.util.Queue;

import Tree.sortedArrayToBST;

/**
 * Lets assume Q1: [1 4 3 2] and Q2: [8 6 5 7] are the two queues where the 
	left most is head of line. I just show the steps 
1- (dequeue Q2 into Q1) 
Q1:[1 4 3 2 8 6 7 5] Q: [] (nQ2inQ1 = 4, nQ1inQ1 = 4) 
2- Dequeue the first the head of line in Q1 into Q2. 
Q1:[4 3 2 8 6 7 5] Q2:[1] (nQ1inQ1 = 3) 
3- Dequeue all the elements from Q1. If it is larger than the last element 
entering Q2, enqueue into Q2, otherwise, enqueue into Q1. 
Q1:[3 2 8 6 7 5] Q2:[1 4] nQ1inQ1 = 3, nQ2inQ1 = 4, nQ1inQ2 = 2, 
last_entered_Q2 = 4 
Q1:[2 8 6 7 5 3] Q2:[1 4] nQ1inQ1 = 3, nQ2inQ1 = 4, nQ1inQ2 = 2, 
last_entered_Q2 = 4 
Q1:[8 6 7 5 3 2] Q2:[1 4]. 
4- Dequeue Q2 into Q1. 
Q1:[8 6 7 5 3 2 1 4] Q2:[] nQ2inQ1 = 4, nQ1inQ1 = 4. 
5- Repeat the process again for elements of Q2. You eventually get: 
Q1[3 2 1 4 6 7 5 8] Q2:[] 
6- Again doing it for elements of Q1. We get at the end 
Q1[6 7 5 8 2 1 3 4] Q2:[] 
7- Again (for Q2) 
Q1[2 1 3 4 5 6 7 8] Q:[] (note that Q2 is sorted now) 
8- Again (for Q1) 
Q1:[5 6 7 8 1 2 3 4] Q:[] 
9- In this round, we realize that Q2 is sorted. (no inversions) 
10- In the next step, we find that Q1 is also sorted.
 *
 */

public class sort2Queue_without_space {
	
	/**
	 * Sort two queue without extra container, Time Complexity O((n1 + n2)^2) worst case.
	 * @param q1 -----------Q1 source queue
	 * @param q2------------Q2 destination queue
	 */
	public static void Sort(Queue<Integer> q1, Queue<Integer> q2){
		int src_len = q1.size();
		int det_len = q2.size();
		int pre;// the last one move to the Q2
		int n= 0; // how many queues have been sorted
		boolean is_work_q1 = true; //whether the process working on Q1
		
		
		while(n<2){
			while(!q2.isEmpty())
				q1.add(q2.poll());
			pre = q1.poll();
			q2.add(pre);
			boolean isSorted = true;
			int n_out = is_work_q1 ? src_len -1 : det_len -1;

			for(int i=0;i<n_out;++i){
				int cur = q1.poll();
				if(cur>pre){
					pre = cur;
					q2.add(cur);
				}
				else{
					isSorted = false;
					q1.add(cur);
				}
			}
			
			is_work_q1 = !is_work_q1;
			if(isSorted)
				n++;
		}
	}
	
	

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] src = {10,3,5,2,8,4};
		int[] dst = {9,3,4,1,2,12,33,98,20};
		ArrayDeque<Integer> source = new ArrayDeque<>();
		ArrayDeque<Integer> destination = new ArrayDeque<>();
		for(int i=0;i<src.length;++i){
			source.add(src[i]);
		}
		for(int i=0;i<dst.length;++i){
			destination.add(dst[i]);
		}
		
		Sort(source, destination);
		
		System.out.println("Source: \n");
		while(!source.isEmpty()){
			System.out.print(source.poll().toString() + " ");
		}
		System.out.println();
		
		System.out.println("Destination: \n");
		while(!destination.isEmpty()){
			System.out.print(destination.poll().toString() + " ");
		}
		System.out.println();
	}

}
